package com.explorati.interview.interview.chapterfifteen.sort.quicksort;

public class QuickSortPractice {

	private QuickSortPractice() {
	}

	public static void sort(Comparable[] arr) {
		int n = arr.length;
		sort(arr, 0, n - 1);
	}

	private static void sort(Comparable[] arr, int l, int r) {
		if (r - l <= 15) {
			InsertionSort.sort(arr, l, r);
		}

		int p = partition(arr, l, r);
		sort(arr, l, p - 1);
		sort(arr, p + 1, r);
	}

	private static int partition(Comparable[] arr, int l, int r) {

		swap(arr, l, (int) Math.random() * (r - l + 1) + l);
		Comparable e = arr[l];

		// int j = l;
		// for (int i = l + 1; i <= r; i++) {
		// if (arr[i].compareTo(e) < 0) {
		// j++;
		// swap(arr, j, i);
		// }
		// }
		// swap(arr, l, j);

		// 双路选择快速排序，解决相同元素的问题
		int i = l + 1, j = r;
		while (true) {
			while (i <= r && arr[i].compareTo(e) < 0) {
				i++;
			}
			while (j >= l + 1 && arr[j].compareTo(e) > 0) {
				j--;
			}
			if (i > j) {
				break;
			}
			swap(arr, i, j);
			i++;
			j--;
		}
		swap(arr, l, j);
		return j;
	}

	private static void swap(Comparable[] arr, int a, int b) {
		Comparable temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}
